1. Field of the Invention
The present invention relates to a content addressable memory (hereinafter referred to as a “CAM”), and in particular, to a priority encoder for use in a CAM.
2. Description of the Related Art
FIG. 13 is a circuit block diagram showing a CAM 10 as an example of a conventional CAM.
The CAM 10 shown in FIG. 13 includes a plurality of word memories 11a, 11b, . . . , 11n storing a bit pattern for one word. The CAM 10 includes a search data register 12 for latching one word of input search data. All or predetermined part of the bit pattern of search data latched by the register 12 is compared with the bit pattern of a portion of data stored in each word memory which corresponds to the all or a predetermined part of the bit pattern. This detects matching/mismatching between the two. Match/mismatch signals (also called “hit signals”) representing matching or mismatching are output from the word memories 11a to 11n, and are stored in flag registers 13a, 13b, . . . , 13n provided for the word memories 11a to 11n, respectively. For example, in a flag-register for a word memory storing data, a portion of which matches the bit pattern of the search data, a high level flag representing matching is stored. In the other flag registers, low level flags representing mismatching are stored. The flag registers 13a to 13n output hit signals Sh to an address encoder 14. Based on the hit signals Sh, the address encoder 14 outputs the address AD of the word memory storing the high level flag. The address AD output from the address encoder 14 is input to an address decoder 15, if needed. The address decoder 15 decodes the input address AD and activates a word memory line among word memory lines 16a, 16b, . . . , 16n, which corresponds to the input address AD. This allows an output register 17 to read the data stored in a word memory connected to the activated word line.
As described above, the CAM 10 can perform searching for data stored in the word memories 11a to 11n by using all or a predetermined part of search data, obtaining the address of a word memory storing data, which matches the search data, and reading the entirety of the data stored in the word memory.
However, the number of word memories storing data which matches the all or predetermined part of the search data is not limited to one, but may be more than one. Accordingly, as the address encoder 14 in the CAM 10, a priority encoder is provided in which predetermined fixed priority order is assigned to the word memories 11a to 11n. When a plurality of word memories store data items matching all or predetermined part of search data, the priority encoder outputs sequentially the addresses AD of the word memories in accordance with the fixed priority order.
Recently, the increased memory capacity have brought about a case in which data items of two themes, for example, are stored by theme in a single CAM, and after data searching, addresses of words which store data item belonging to one theme needs to be output prior to other addresses as the search result.
FIG. 14 is a schematic illustration of a state in which data items of two themes are stored by theme in a conventional CAM.
Referring to FIG. 14, the data items of theme A are stored in upper word memories 11a, 11b, . . . , 11m−1, while the data items of theme B are stored in lower word memories 11m, . . . , 11n. 
Here, the conventional CAM outputs the addresses of word memories obtained by searching in accordance with fixed priority order in the priority encoder. In FIG. 14, as indicated by the arrow, the priority order is represented in the order of the subscripted alphabetical letters of reference numerals denoting the word memories 11a to 11m−1, and 11m to 11n. In this case, the data items of theme A are stored in the word memories 11a to 11m−1, having higher priority, and the data items of theme B are stored in the word memories 11m to 11n, having lower priority.
Accordingly, in the case of attempting to output an address of word memory belonging to theme B prior to an address of word memory belonging to theme A, or to output only an address having the highest priority for the theme B, the conventional CAM sequentially outputs addresses in accordance with the fixed priority order in the priority encoder, regardless of the themes of stored data items.
Also, in the case of attempting to output only the addresses of word memories belong to theme B, the result of searching for the data items of theme B must be output after the result of searching for the data items of theme A, which is not necessary, is completely output.
In order for the conventional CAM to start to output the searching results for the data items of theme B, which is desired by a user, for example, in one method, before data searching is performed, data items stored in the CAM need to be arranged so that words storing the data items of theme B have higher priority and words storing the data items of theme A have lower priority. Also, in another method, after the results of searching are output from the CAM, the output results are rearranged so that the result of searching the data items of theme B has higher priority and the result of searching the data items of theme A has lower priority. However, these methods have a problem of complication in managing the data stored in the CAM and the results of searching output from the CAM.